The just-in-time (JIT) compilation model for the JAVA programming language (henceforth referred to as “JAVA”) is an impediment to generating code that is as efficient as code generated using static optimization. Sophisticated static compilers for C++ perform whole program analysis, optimization, and transformation, to generate efficient code. Whole program analysis is possible for the C++ language, since C++ does not allow new classes and/or methods to be loaded during program executions. In C++, when faced with calls to methods whose bodies are not known during compile time, such as Dynamic Link Libraries (DLLs), these static compilers usually make conservative assumptions about the methods.
In JAVA, new classes can be loaded “on-the-fly” during program execution, as noted by Bracha et al., in “Dynamic Class Loading in the JAVA Virtual Machine”, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, October 1998. Attempting to apply the C++ whole program static analysis framework to JAVA can result in an incorrect program. For example, consider a virtual call p.foo( ). In C++, whole program analysis can be used to determine whether a virtual call has only one target, as described by Bacon et al., in “Fast Static Analysis of C++ Virtual Function Calls”, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 324-41, October 1996. If so, the virtual call can be directly converted to a static call (and the call possibly inlined). Attempting to do such devirtualization in JAVA (without a runtime type check guarding the devirtualization) can result in an incorrect program because, during execution, a new class can be loaded and p.foo( ) can invoke a new foo( ) in the newly loaded class.
One solution for avoiding incorrect execution after a new class is loaded is to invalidate and recompile affected methods, as described by: Chambers et al., in “Debugging Optimized Code with Dynamic Deoptimization”, SIGPLAN '92 Conference on Programming Language Design and Implementation, SIGPLAN Notices 27(6), June 1992; Holzle et al., in “A Third Generation Self Implementation: Reconciling Responsiveness with Performance”, ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 229-43, October 1994; Craig Chambers, “The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages”, PhD thesis, Stanford University, March 1992; and Burke et al., in “Interprocedural Optimization: Eliminating Unnecessary Recompilation”, ACM Transactions on Programming Languages and Systems, 15(3):367-399, July 1993.
However, runtime invalidation and recompilation mechanisms have several drawbacks, such as: (1) they can be expensive in both space and time; (2) the activation stack frame for active and invalidated methods may have to be rewritten; (3) they can restrict how much optimization one allowed to do so that invalidation can be correctly applied during runtime; and (4) a complex and an expensive synchronization mechanism may be needed to correctly invalidate methods in a multithreaded environment. The second disadvantage is further described by Chambers et al., in “Debugging Optimized Code with Dynamic Deoptimization”, SIGPLAN '92 Conference on Programming Language Design and Implementation, SIGPLAN Notices 27(6), June 1992. The third disadvantage is further described in the immediately preceding article by Chambers et al., and also by Craig Chambers, in “The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages”, PhD thesis, Stanford University, March 1992. The fourth disadvantage is further described by Alpern et al., in “Dynamic Linking on a Shared-Memory Multiprocessor”, International Conference on Parallel Architectures and Compilation Techniques, October 1999.
Accordingly, there is a need for a method that optimizes an object oriented program in the presence of dynamic class and/or method loading.